package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.HeapProblem;

import java.util.Arrays;
import java.util.Objects;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveTask;

/**
 * FJPool
 *
 * @author tzp
 * @since 2020/10/15
 */
public class LC23_1 implements HeapProblem {

    public ListNode mergeKLists(ListNode[] arr) {
        if (arr == null || arr.length == 0) return null;
        arr = Arrays.stream(arr).filter(Objects::nonNull).toArray(ListNode[]::new);
        ForkJoinTask<ListNode> task = ForkJoinPool.commonPool().submit(new MergeTask(arr, 0, arr.length));
        try {
            return task.get();
        } catch (Exception e) {
            e.printStackTrace();
            return null;
        }
    }

    class MergeTask extends RecursiveTask<ListNode> {
        ListNode[] arr;
        int start;
        int end;//exclude

        public MergeTask(ListNode[] arr, int start, int end) {
            this.arr = arr;
            this.start = start;
            this.end = end;
        }

        @Override
        protected ListNode compute() {
            if (end - start <= 1) return arr[start];
            if (end - start == 2) {
                return mergeTwoLists(arr[start], arr[start + 1]);
            } else {
                int mid = (start + end) / 2;
                MergeTask task1 = new MergeTask(arr, start, mid);
                task1.fork();
                MergeTask task2 = new MergeTask(arr, mid, end);
                task2.fork();
                return mergeTwoLists(task1.join(), task2.join());
            }
        }

        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if (l1 == null) return l2;
            else if (l2 == null) return l1;
            ListNode dummy = new ListNode(0);
            ListNode curr = dummy;
            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    curr.next = l1;
                    l1 = l1.next;
                } else {
                    curr.next = l2;
                    l2 = l2.next;
                }
                curr = curr.next;
            }
            curr.next = l1 == null ? l2 : l1;
            return dummy.next;
        }
    }


    public static void main(String[] args) {
        ListNode a = ListNode.arrayToListNode(new int[]{1, 4, 5});
        ListNode b = ListNode.arrayToListNode(new int[]{3, 3, 4});
        ListNode c = ListNode.arrayToListNode(new int[]{2, 6});
        System.out.println(new LC23_1().mergeKLists(new ListNode[]{a, b, c}));
    }
}
